Longest palindromic subsequence

Time: O(N^2); Space: O(N); medium

Given a string s, find the longest palindromic subsequence’s length in s.

You may assume that the maximum length of s is 1000.

Example 1:

Input: s = “bbbab”

Output: 4

Explanation:

  • One possible longest palindromic subsequence is “bbbb”.

Example 2:

Input: s = “cbbd”

Output: 2

Explanation:

  • One possible longest palindromic subsequence is “bb”.

Constraints:

  • 1 <= len(s) <= 1000

  • s consists only of lowercase English letters.

[1]:

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == s[::-1]:  # optional, to optimize special case
            return len(s)

        dp = [[1] * len(s) for _ in range(2)]

        for i in reversed(range(len(s))):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    dp[i%2][j] = 2 + dp[(i+1)%2][j-1] if i+1 <= j-1 else 2
                else:
                    dp[i%2][j] = max(dp[(i+1)%2][j], dp[i%2][j-1])

        return dp[0][-1]

[2]:

sol = Solution1()

s = "bbbab"
assert sol.longestPalindromeSubseq(s) == 4

s = "cbbd"
assert sol.longestPalindromeSubseq(s) == 2